#{extends 'main.html' /}
#{set title:'Overclocking' /}

#{doBody /}

<html>
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
    <script type="text/javascript" src="jquery.js"></script>
</head>
<body>
<div>
    <p>Overclocking</p>

    <div>

        <div>
            <p>В настоящее время алгоритмы обрабатывающие большие объемы данных привлекают все больше внимания. Причина
                не только
                в том, что с каждым днем растет объем доступных данных. Так, например, в
                области машинного обучения привлечение большего
                объема данных позволяет увеличить точность получаемой модели. Один из
                подходов позволяющих снизить скорость
                роста размера входных данных заключается в работе со сжатыми
                представлениями.
            </p>

            <p>
                Известны различные сжатые представления данных: прямолинейные программы
                (кратко ПП), коллаж
                системы, представления данных с помощью антисловарей и т.д. В настоящее
                время
                сжатие текста с помощью контекстно-свободных грамматик (таких как ПП)
                является активно развивающимся направлением
                научных исследований. Причина этого не только в том, что грамматики
                обеспечивают хорошо-структурированное сжатие
                данных, но и в том, что сжатие с помощью ПП в некотором смысле полиномиально
                эквивалентно сжатию данных с помощью
                алгоритма Лемпеля-Зива. Другими словами, существует полиномиальная
                зависимость между размером ПП, выводящей заданный
                текст S, и размером словаря, построенным алгоритмом Лемпеля-Зива для текста
                S. Заметим, что классические алгоритмы сжатия LZ78
                и LZW являются частными случаями грамматического сжатия. При этом другие
                алгоритмы из семейства алгоритмов Лемпеля-Зива, например LZ77
                и кодирование повторов, не укладываются в модель грамматического сжатия.
            </p>

            <p>
                Поскольку ПП обеспечивают хорошо-структурированное представление данных, то
                возникает идея решать классические строковые
                задачи в терминах ПП. Существует класс алгоритмов, которые решают следующие
                строковые задачи в терминах ПП:
                Поиск образца в тексте, Наибольшая общая подстрока, считающая версия задачи
                Поиск всех палиндромов, разновидность задачи Наибольшая общая
                подпоследовательность. В тоже время константы, которые скрываются за
                определением функции O в оценке сложности таких
                алгоритмов, как правило очень большие. Также полиномиальная связь между
                размером ПП, выводящей заданный текст S, и
                размером LZ77-словаря для этого же текста S еще не гарантирует, что ПП
                обеспечивают высокую степень сжатия на
                практике. Поэтому актуальным становится следующий вопрос: существуют ли
                модели сжатия с помощью ПП эффективно
                работающие на практике? В работе детально рассматриваются два вопроса.
                Насколько трудно строить ПП на
                практике? Насколько высокий уровень сжатия обеспечивают ПП относительно
                классических алгоритмов сжатия на практике?
            </p>
        </div>
        <div>
            <a href="/Statistic/filesInfo">Список загруженных файлов</a>
            <a href="/Statistic/graphics">Посмотреть статистику</a>
        </div>
    </div>
</div>
</body>
</html>
